Heap sort - O(NLog(N))

This popular sorting algorithm, like the Insertion and Selection sorts,

segments the List into Sorted and Unsorted parts.

It converts the Unsorted segment of the List to a Heap data structure,

so that we can efficiently determine the Largest element.

Explanation:

We begin by transforming the list into a Max Heap -

a Binary Tree where the biggest element is the root node.

We then place that item to the end of the list.

We then rebuild our Max Heap which now has one less value,

placing the new largest value before the last item of the list.

We iterate this process of building the heap until all nodes are removed.

Time Complexity:

Let’s first look at the time complexity of the heapify function.

In the worst case the largest element is never the root element,

this causes a recursive call to heapify.

While recursive calls might seem dauntingly expensive,

remember that we’re working with a binary tree.

Visualize a binary tree with 3 elements, it has a height of 2.

Now visualize a binary tree with 7 elements, it has a height of 3.

The tree grows logarithmically to N.

The heapify function traverses that tree in O(Log(N)) time.

The heap_sort function iterates over the array N times.

Therefore the overall time complexity of the Heap Sort algorithm is

O(NLog(N)).

def heapify(L, heap_size, root_index):

    # Assume the index of the largest element is the root index
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2

    # If the left child of the root is a valid index, and the element is greater
    # than the current largest element, then update the largest element
    if left_child < heap_size and L[left_child] > L[largest]:
        largest = left_child

    # Do the same for the right child of the root
    if right_child < heap_size and L[right_child] > L[largest]:
        largest = right_child

    # If the largest element is no longer the root element, swap them
    if largest != root_index:
        L[root_index], L[largest] = L[largest], L[root_index]

        # Heapify the new root element to ensure it's the largest
        heapify(L, heap_size, largest)


def heap_sort(L):
    N = len(L)

    # Create a Max Heap from the List
    # The 2nd argument of range means we stop at the element before -1
    # i.e. the first element of the List.
    # The 3rd argument of range means we iterate backwards,
    # reducing the count of i by 1
    for i in range(N, -1, -1):
        heapify(L, N, i)

    # Move the root of the Max Heap to the end
    for i in range(N - 1, 0, -1):
        L[i], L[0] = L[0], L[i]
        heapify(L, i, 0)

Test:

random_LON = [35, 12, 43, 8, 51]
heap_sort(random_LON)
print(random_LON)

See also

https://stackabuse.com/sorting-algorithms-in-python/